package Heap;

import sun.awt.util.IdentityArrayList;

import java.util.*;

/**
 * topK
 */

class Imp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}


public class Test {
    /**
     * 找到前K个最小的数据
     * @param array
     * @param k
     * @return
     * 这个代码不是真正解决topK问题的方法
     */
    public static int[] smallestKey1(int[] array,int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        //O(N)
        for (int x : array) {
            minHeap.offer(x);
        }
        //小根堆中，已经把所有元素存起来了
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }

        return ret;
    }

        //方法2：前面还写了个Imp接口,找最小建大堆
        //时间复杂度：NlogK
        public static int[] smallestKey(int[] array,int k) {
        int[] ret = new int[k];
        if(k == 0) {
            return ret;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Imp());
        for(int i = 0; i < k; i ++) {
            maxHeap.offer(array[i]);
        }

        for(int i = k; i < array.length; i++) {
            //获取堆顶元素的值
            int top = maxHeap.peek();
            if(top > array[i]) {
                maxHeap.poll();
                maxHeap.offer(array[i]);
            }
        }

        for(int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }

        return ret;
    }



    public static void main(String[] args) {
        Heap heap = new Heap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        heap.createHeap(array);

        //heap.push(80);
        //heap.poll();
        heap.HeapSort();
        System.out.println();

    }
}
